{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #N-Queens"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: solveNQueens"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #N 皇后"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。</p>\n",
    "\n",
    "<p><strong>n&nbsp;皇后问题</strong> 研究的是如何将 <code>n</code>&nbsp;个皇后放置在 <code>n×n</code> 的棋盘上，并且使皇后彼此之间不能相互攻击。</p>\n",
    "\n",
    "<p>给你一个整数 <code>n</code> ，返回所有不同的&nbsp;<strong>n<em>&nbsp;</em>皇后问题</strong> 的解决方案。</p>\n",
    "\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<p>每一种解法包含一个不同的&nbsp;<strong>n 皇后问题</strong> 的棋子放置方案，该方案中 <code>'Q'</code> 和 <code>'.'</code> 分别代表了皇后和空位。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/11/13/queens.jpg\" style=\"width: 600px; height: 268px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4\n",
    "<strong>输出：</strong>[[\".Q..\",\"...Q\",\"Q...\",\"..Q.\"],[\"..Q.\",\"Q...\",\"...Q\",\".Q..\"]]\n",
    "<strong>解释：</strong>如上图所示，4 皇后问题存在两个不同的解法。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1\n",
    "<strong>输出：</strong>[[\"Q\"]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 9</code></li>\n",
    "</ul>\n",
    "</div>\n",
    "</div>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [n-queens](https://leetcode.cn/problems/n-queens/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [n-queens](https://leetcode.cn/problems/n-queens/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4', '1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        ans = []\n",
    "        \n",
    "        def backtracking(row, arra):\n",
    "            if row == n:\n",
    "                ans.append(list(arra))\n",
    "                return\n",
    "            \n",
    "            for col in range(n):\n",
    "                if not isValid(arra, row, col): continue\n",
    "                \n",
    "                arra[row] = arra[row][:col]+'Q'+arra[row][col+1:]\n",
    "                backtracking(row+1, arra)\n",
    "                arra[row] = arra[row][:col]+'.'+arra[row][col+1:]\n",
    "        \n",
    "        def isValid(arra, row, col):\n",
    "            for i in range(row+1):\n",
    "                if arra[i][col] == 'Q': return False\n",
    "            r, c = row-1, col+1\n",
    "            while r>=0 and c<n:\n",
    "                if arra[r][c] == 'Q': return False\n",
    "                r -= 1\n",
    "                c += 1\n",
    "            r, c = row-1, col-1\n",
    "            while r>=0 and c>=0:\n",
    "                if arra[r][c] == 'Q': return False\n",
    "                r -= 1\n",
    "                c -= 1\n",
    "            return True\n",
    "            \n",
    "            \n",
    "        init = ['.'*n for i in range(n)]\n",
    "        backtracking(0, init)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def solveNQueens(self, n):\n",
    "        res = []\n",
    "        self.dfs([-1]*n, 0, [], res)\n",
    "        return res\n",
    "\n",
    "    # nums is a one-dimension array, like [1, 3, 0, 2] means\n",
    "    # first queen is placed in column 1, second queen is placed\n",
    "    # in column 3, etc.\n",
    "    def dfs(self, nums, index, path, res):\n",
    "        if index == len(nums):\n",
    "            res.append(path)\n",
    "            return  # backtracking\n",
    "        for i in range(len(nums)):\n",
    "            nums[index] = i\n",
    "            if self.valid(nums, index):  # pruning\n",
    "                tmp = \".\"*len(nums)\n",
    "                self.dfs(nums, index+1, path+[tmp[:i]+\"Q\"+tmp[i+1:]], res)\n",
    "\n",
    "    # check whether nth queen can be placed in that column\n",
    "    def valid(self, nums, n):\n",
    "        for i in range(n):\n",
    "            if abs(nums[i]-nums[n]) == n -i or nums[i] == nums[n]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[List[str]]\n",
    "        \"\"\"\n",
    "        def DFS(resIndex, index, dif, sums, n):\n",
    "            c = len(index)\n",
    "            if c >= n:\n",
    "                resIndex.append(index)\n",
    "                return\n",
    "            for l in range(n):\n",
    "                if (l not in index) and (c - l not in dif) and (c + l not in sums): \n",
    "                    DFS(resIndex, index + [l], dif + [c - l], sums + [c + l], n)  \n",
    "        resIndex = []\n",
    "        DFS(resIndex ,[], [], [], n)\n",
    "        res = []\n",
    "        for i in resIndex:\n",
    "            tmp = []\n",
    "            for j in i:\n",
    "                tmp.append(\".\" * j + \"Q\" + \".\" * (n - j - 1))\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: 'int') -> 'List[List[str]]':\n",
    "        def Dfs(queue,xy_dif,xy_sum):\n",
    "            p = len(queue)\n",
    "            if p == n:\n",
    "                result.append(queue)\n",
    "                return\n",
    "            for q in range(n):\n",
    "                if q not in queue and p-q not in xy_dif and p+q not in xy_sum:\n",
    "                    Dfs(queue+[q],xy_dif+[p-q],xy_sum+[p+q])\n",
    "        result = []\n",
    "        Dfs([],[],[])\n",
    "        return [['.'*i + 'Q' + '.'*(n-i-1) for i in sol] for sol in result]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[List[str]]\n",
    "        \"\"\"\n",
    "        #建立一个list（长度8）存放每行女王的列\n",
    "        self.res=[]\n",
    "        self.help=[\".\"]*n\n",
    "        def conflict(i,list1):\n",
    "            if i in list1:\n",
    "                return True\n",
    "            p=len(list1)\n",
    "            for index,val in enumerate(list1):\n",
    "                if index-val==p-i or index+val==p+i:\n",
    "                    return True\n",
    "            return False\n",
    "        def backtract(list1):\n",
    "            if len(list1)==n:\n",
    "                self.res.append([\"\".join(self.help[:i]+['Q']+self.help[i+1:]) for i in list1])\n",
    "                return\n",
    "            for index in range(n):\n",
    "                if not conflict(index,list1):\n",
    "                    backtract(list1+[index])\n",
    "        backtract([])\n",
    "        return self.res\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        \n",
    "        res = []\n",
    "        \n",
    "        # loc 表示皇后位置的纵坐标，从第一行到第n行依次排列\n",
    "        def dfs(loc=(0,)):\n",
    "            \n",
    "            # 判断皇后当前位置是否合理\n",
    "            last_row, last_col = len(loc)-1, loc[-1]\n",
    "            for row, col in enumerate(list(loc)[:-1]):\n",
    "                if abs(last_row-row) == abs(last_col-col):\n",
    "                    return\n",
    "                \n",
    "            # 位置合理，并且n行都占有了，记录并退出\n",
    "            if len(loc) == n:\n",
    "                res.append(['.'*i+'Q'+'.'*(n-1-i) for i in loc])\n",
    "                return\n",
    "            \n",
    "            # 位置合理，不足n行，继续寻找下一个可能的位置\n",
    "            for idx in range(n):\n",
    "                if idx not in loc:\n",
    "                    dfs(loc+(idx,))\n",
    "                    \n",
    "        for first in range(n):\n",
    "            dfs((first,))\n",
    "\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self):\n",
    "        # 初始变量，减少函数传递次数\n",
    "        # 记录列的情况，表示是否被占用,Ture表示被占用，False表示空\n",
    "        self.coloccupied = []\n",
    "        # 记录左对角线的情况，表示左对角线是否被占用\n",
    "        self.Left_diag = []\n",
    "        # 记录又对角线的情况，表示右边的对角线是否被占用\n",
    "        self.right_diag = []\n",
    "        # 皇后的面板，所有的位置都初始化为'.'\n",
    "        self.board = []\n",
    "        # 矩阵维度\n",
    "        self.rank = 0\n",
    "        # 结果数组\n",
    "        self.res = []\n",
    "\n",
    "    def solveNQueens(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[List[str]]\n",
    "        \"\"\"\n",
    "        self.rank = n\n",
    "        self.coloccupied = [False]*self.rank\n",
    "        self.Left_diag = [False]*(2*self.rank-1)\n",
    "        self.right_diag = [False]*(2*self.rank-1)\n",
    "        for _ in range(self.rank):\n",
    "            self.board.append(['.']*self.rank)\n",
    "        self.nQueen(0)\n",
    "\n",
    "        for i in range(len(self.res)):\n",
    "            self.res[i] = [''.join(subitem) for subitem in self.res[i]]\n",
    "        # for item in self.res:\n",
    "        #     item =[''.join(subitem) for subitem in item]\n",
    "            # for i in range(self.rank):\n",
    "            #     item[i] = ''.join(item[i])\n",
    "        return self.res\n",
    "\n",
    "    # 检查当前位置是否被占用，被占用返回Ture，没有被占用返回False\n",
    "    def isOccupied(self, row, col):\n",
    "        # 当前位置所在的列，左对角线，右对角线只要有一个被占用，则该位置就被占用\n",
    "        return self.coloccupied[col] or self.Left_diag[row+col] or self.right_diag[row+self.rank-col-1]\n",
    "\n",
    "    def put(self, row, col, isput):\n",
    "        # 该列是否被占用\n",
    "        self.coloccupied[col] = isput\n",
    "        # 该位置左对角线是否被占用\n",
    "        self.Left_diag[row+col] = isput\n",
    "        # 该位置右对角线是否被占用\n",
    "        self.right_diag[row+self.rank-col-1] = isput\n",
    "        # 如果是放置，则放入\"Q\"，清空，放置\".\"\n",
    "        self.board[row][col] = \"Q\" if isput else \".\"\n",
    "\n",
    "    def nQueen(self, row):\n",
    "        if row == self.rank:\n",
    "            self.res.append(copy.deepcopy(self.board))\n",
    "            return\n",
    "        for col in range(self.rank):\n",
    "            if self.isOccupied(row, col):\n",
    "                continue\n",
    "            self.put(row, col, True)\n",
    "            self.nQueen(row+1)\n",
    "            self.put(row, col, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[List[str]]\n",
    "        \"\"\"\n",
    "        \n",
    "        line = []\n",
    "        row = []\n",
    "        zuoxie = []\n",
    "        youxie = []\n",
    "        for i in range(n):\n",
    "            line.append(0)\n",
    "            row.append(0)\n",
    "        for i in range(2*n -1):\n",
    "            zuoxie.append(0)\n",
    "            youxie.append(0)\n",
    "            \n",
    "        res = []\n",
    "        def place(line, row, zuoxie, youxie, index, temp, n):\n",
    "            for x in range(n):\n",
    "                #判断n行x列是否可以放：\n",
    "                #判断行，列，左斜右斜是否有皇后\n",
    "                you = index-x if x+index >= 0 else abs(index-x)+n-1\n",
    "                print(index, x, x+index, you)\n",
    "                if line[index] == 0 and row[x] == 0 and zuoxie[x+index] == 0 and youxie[you] == 0:\n",
    "                    #可以就放置\n",
    "                    line[index], row[x], zuoxie[x+index], youxie[you] = 1,1,1,1\n",
    "                    #制作st\n",
    "                    st = \"\"\n",
    "                    for p in range(x):\n",
    "                        st += '.'\n",
    "                    st += 'Q'\n",
    "                    for p in range(x+1, n):\n",
    "                        st += '.'\n",
    "                    temp.append(st)\n",
    "                    #若成功放置最后一个,加入结果 \n",
    "                    if index == n-1:\n",
    "                        res.append(copy.deepcopy(temp))\n",
    "                    else:\n",
    "                        #放下一个\n",
    "                        temp = place(line, row, zuoxie, youxie, index+1, temp, n)\n",
    "                    \n",
    "                    #尝试下一个位置放置:\n",
    "                    line[index], row[x], zuoxie[x+index], youxie[you] = 0,0,0,0\n",
    "                    temp.remove(st)\n",
    "            #所有位置尝试完毕        \n",
    "            return temp\n",
    "        \n",
    "        place(line,row,zuoxie,youxie,0,[],n)\n",
    "        return res\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[List[str]]\n",
    "        \"\"\"\n",
    "        rets = []\n",
    "        dic = {tuple([-1 for i in range(n)]):([], [])}\n",
    "        for x in range(n):\n",
    "            dic = self.f(dic, x, n)\n",
    "        for key in dic:\n",
    "            ret = [''.join('.' if i != y else 'Q' for i in range(n)) for y in key]\n",
    "            rets.append(ret)\n",
    "        return rets\n",
    "    \n",
    "    def f(self, dic, x, n):\n",
    "        temps = {}\n",
    "        for key in dic:\n",
    "            for i in range(n):\n",
    "                if i + x in dic[key][0] or i - x in dic[key][1] or key[i] != -1:\n",
    "                    continue\n",
    "                temp = list(key)\n",
    "                temp[i] = x\n",
    "                temps[tuple(temp)] = (dic[key][0] + [i + x], dic[key][1] + [i - x])\n",
    "        return temps"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __backtracking(self, i, npos, n, result):\n",
    "        for j in range(n):\n",
    "            if self.__ck(npos, i, j):\n",
    "                npos[(i, j)] = ''\n",
    "                if i == n-1:\n",
    "                    m = [['Q' if (x, y) in npos else '.' for y in range(n)] for x in range(n)]\n",
    "                    result.append([''.join(x) for x in m])\n",
    "                else:\n",
    "                    self.__backtracking(i+1, npos, n, result)\n",
    "                npos.pop((i, j))\n",
    "    def __ck(self, npos, x, y):\n",
    "        for (i, j) in npos.keys():\n",
    "            if i == x or j == y or abs(i-x) == abs(j-y):\n",
    "                return False\n",
    "        return True\n",
    "    def solveNQueens(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[List[str]]\n",
    "        \"\"\"\n",
    "        if n == 1:\n",
    "            return [['Q']]\n",
    "        if n == 2 or n == 3:\n",
    "            return []\n",
    "        result = []\n",
    "        self.__backtracking(0, dict(), n, result)\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。\n",
    "#\n",
    "# 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。\n",
    "#\n",
    "# 每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。\n",
    "import copy\n",
    "class Solution:\n",
    "\tdef solveNQueens(self, n):\n",
    "\t\t\"\"\"\n",
    "\t\t:type n: int\n",
    "\t\t:rtype: List[List[str]]\n",
    "\t\t\"\"\"\n",
    "\t\tself.out = []\n",
    "\t\tself.n = n\n",
    "\t\t#初始化棋盘\n",
    "\t\tcheck = [['.' for _ in range(n)] for _ in range(n)]\n",
    "\t\t#递归\n",
    "\t\tfor k in range(1,n+1):\n",
    "\t\t\tself.recurs_setQueen(copy.deepcopy(check),n,1,k)\n",
    "\t\treturn self.out\n",
    "\tdef setQueen(self,check,rows,i):\n",
    "\t\t#在rows行,i列设置皇后\n",
    "\t\tcheck[rows-1][i-1] = 'Q'\n",
    "\tdef isLegal(self,check,rows,i):\n",
    "\t\t#检查一列有没有皇后\n",
    "\t\tr = rows-2\n",
    "\t\tc = i-1\n",
    "\t\twhile not (r == -1):\n",
    "\t\t\tif check[r][c] == 'Q':\n",
    "\t\t\t\treturn False\n",
    "\t\t\tr -= 1\n",
    "\t\t#检查对角线\n",
    "\t\tr = rows-2\n",
    "\t\tc = i-2\n",
    "\t\twhile not ((r==-1) | (c == -1)):\n",
    "\t\t\tif check[r][c] == 'Q':\n",
    "\t\t\t\treturn False\n",
    "\t\t\tr -= 1\n",
    "\t\t\tc -= 1\n",
    "\t\tr = rows-2\n",
    "\t\tc = i\n",
    "\t\twhile not ((r==-1) | (c == self.n)):\n",
    "\t\t\tif check[r][c] == 'Q':\n",
    "\t\t\t\treturn False\n",
    "\t\t\tr -= 1\n",
    "\t\t\tc += 1\n",
    "\t\treturn True\n",
    "\tdef display(self,check):\n",
    "\t\tlist = []\n",
    "\t\tfor i in check:\n",
    "\t\t\tlist.append(''.join(i))\n",
    "\t\tself.out.append(list)\n",
    "\tdef recurs_setQueen(self,check,n,rows,cols):\n",
    "\t\tself.setQueen(check,rows, cols)\n",
    "\t\tif self.isLegal(check,rows, cols) == False:\n",
    "\t\t\treturn\n",
    "\n",
    "\t\tif rows == n:\n",
    "\t\t\tself.display(check)\n",
    "\t\t\treturn\n",
    "\t\tfor i in range(1,n+1):\n",
    "\t\t\tself.recurs_setQueen(copy.deepcopy(check),n,rows+1,i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import permutations\n",
    "class Solution:\n",
    "    def solveNQueens(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[List[str]]\n",
    "        \"\"\"\n",
    "        cols = range(n)\n",
    "        ans_list = []\n",
    "        for vec in permutations(cols):\n",
    "            if (n == len(set(vec[i]+i for i in cols))\n",
    "                  == len(set(vec[i]-i for i in cols))):\n",
    "                ans = []\n",
    "                for i in vec:\n",
    "                    loca = [\".\"] * n\n",
    "                    loca[i] = 'Q'\n",
    "                    ans.append(\"\".join(loca))\n",
    "                ans_list.append(ans)\n",
    "        return ans_list\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        # 判断matrix是否有效\n",
    "        def judge_vaild(matrix, i, j):\n",
    "            # 节点所在列是否重复\n",
    "            tmp = 0\n",
    "            for m in range(len(matrix)):\n",
    "                if matrix[m][j] == 'Q':\n",
    "                    tmp += 1\n",
    "            if tmp > 1:\n",
    "                return False\n",
    "\n",
    "            # 节点的左斜线是否重复\n",
    "            tmp_i, tmp_j = i, j\n",
    "            while tmp_i and tmp_j:\n",
    "                tmp_i, tmp_j = tmp_i - 1, tmp_j - 1\n",
    "                if matrix[tmp_i][tmp_j] == 'Q':\n",
    "                    tmp += 1\n",
    "            if tmp > 1:\n",
    "                return False\n",
    "\n",
    "            # 节点的右斜线是否重复\n",
    "            while i:\n",
    "                i, j = i - 1, j + 1\n",
    "                if j < len(matrix):\n",
    "                    if matrix[i][j] == 'Q':\n",
    "                        tmp += 1\n",
    "                else:\n",
    "                    break\n",
    "            if tmp > 1:\n",
    "                return False\n",
    "            return True\n",
    "        result, matrix = [], ['.' * n for _ in range(n)]\n",
    "        def generate_matrix(matrix, i, n):\n",
    "            if i == len(matrix):\n",
    "                # 满足条件的解法\n",
    "                result.append([_ for _ in matrix])\n",
    "                return None\n",
    "            for j in range(n):\n",
    "                matrix[i] = '.' * j + 'Q' + '.' * (n - j - 1)\n",
    "                if judge_vaild(matrix, i, j):\n",
    "                    generate_matrix(matrix, i + 1, n)\n",
    "                matrix[i] = '.' * n\n",
    "        generate_matrix(matrix, 0, n)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        def check(solution, cur_row):\n",
    "            col = solution[cur_row].index('Q')\n",
    "            for row in range(cur_row):\n",
    "                cur_col = solution[row].index('Q')\n",
    "                if cur_col == col or abs(cur_col-col) == cur_row-row:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        def backtrack(solution, cur_row):\n",
    "            if cur_row == n:\n",
    "                output.append(solution[:])\n",
    "                return\n",
    "\n",
    "            for i in range(n):\n",
    "                solution[cur_row] = '.'*i + 'Q' + '.'*(n-i-1)\n",
    "                if check(solution, cur_row):\n",
    "                    backtrack(solution, cur_row+1)\n",
    "                solution[cur_row] = '.'*n\n",
    "\n",
    "        output = []\n",
    "        init_solution = ['.'*n for i in range(n)]\n",
    "        backtrack(init_solution, 0)\n",
    "        return output\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# @typingMonkey\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        ans = []\n",
    "        def f(a, b, c):\n",
    "            if (j := len(a)) == n:\n",
    "                ans.append(a)\n",
    "            else:\n",
    "                for i in range(n):\n",
    "                    if i not in a and i - j not in b and i + j not in c:\n",
    "                        f([*a, i], [*b, i - j], [*c, i + j])\n",
    "        f([], [], [])\n",
    "        return ((\".\" * i + \"Q\" + \".\" * (n - i - 1) for i in arr) for arr in ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        def could_place(row, col):\n",
    "            return not (cols[col] + hill_diagonals[row - col] + dale_diagonals[row + col])\n",
    "\n",
    "        def place_queen(row, col):\n",
    "            queens.add((row, col))\n",
    "            cols[col] = 1\n",
    "            hill_diagonals[row - col] = 1\n",
    "            dale_diagonals[row + col] = 1\n",
    "\n",
    "        def remove_queen(row, col):\n",
    "            queens.remove((row, col))\n",
    "            cols[col] = 0\n",
    "            hill_diagonals[row - col] = 0\n",
    "            dale_diagonals[row + col] = 0\n",
    "\n",
    "        def add_solution():\n",
    "            solution = []\n",
    "            for _, col in sorted(queens):\n",
    "                solution.append('.' * col + 'Q' + '.' * (n - col - 1))\n",
    "            output.append(solution)\n",
    "\n",
    "        def backtrack(row=0):\n",
    "            for col in range(n):\n",
    "                if could_place(row, col):\n",
    "                    place_queen(row, col)\n",
    "                    if row + 1 == n:\n",
    "                        add_solution()\n",
    "                    else:\n",
    "                        backtrack(row + 1)\n",
    "                    remove_queen(row, col)\n",
    "\n",
    "        cols = [0] * n\n",
    "        hill_diagonals = [0] * (2 * n - 1)\n",
    "        dale_diagonals = [0] * (2 * n - 1)\n",
    "        queens = set()\n",
    "        output = []\n",
    "        backtrack()\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        #track 长度为n的列表， track[x] = y 表示 在第x行选取了 第y列 ，所以判断对角线 row+col ==x+y 斜率为-1的对角线 row - col == x-y 斜率为1的对角线\n",
    "\n",
    "        # def valid(row, col, track):\n",
    "        #     if col in track:  # 判列\n",
    "        #         return False\n",
    "        #     for k in range(row):  # 判斜对角\n",
    "        #         if row + col == k + track[k] or row - col == k - track[k]:\n",
    "        #             return False\n",
    "        #     return True\n",
    "\n",
    "        # def backtrack(row, track):\n",
    "        #     if row == n:  # 已到最后一行\n",
    "        #         res.append(track)\n",
    "        #         return\n",
    "        #     for col in range(n):\n",
    "        #         if valid(row, col, track):  # 若位置合法，则进入下一行\n",
    "        #             backtrack(row + 1, track + [col])\n",
    "\n",
    "        # res = []\n",
    "        # backtrack(0, [])\n",
    "        # return [['.'*i + 'Q' + '.'*(n-i-1) for i in l] for l in res]\n",
    "\n",
    "        def check(nums,new):\n",
    "            for i in range(len(nums)):\n",
    "                if abs(new-nums[i]) in (0,len(nums)-i):\n",
    "                    return False\n",
    "            return True\n",
    "        mapping,ans = ['.'*i + 'Q' + '.'*(n-i-1) for i in range(n)],[]        \n",
    "        def backtrack(nums):\n",
    "            if len(nums)==n:\n",
    "                ans.append([mapping[c] for c in nums])\n",
    "                return \n",
    "            for i in range(n):\n",
    "                if check(nums,i):\n",
    "                    backtrack(nums+[i])\n",
    "        backtrack([])\n",
    "        return ans\n",
    " \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        def check(nums,new):\n",
    "            for i in range(len(nums)):\n",
    "                if abs(new-nums[i]) in (0,len(nums)-i):\n",
    "                    return False\n",
    "            return True\n",
    "        mapping,ans = ['.'*i + 'Q' + '.'*(n-i-1) for i in range(n)],[]        \n",
    "        def backtrack(nums):\n",
    "            if len(nums)==n:\n",
    "                ans.append([mapping[c] for c in nums])\n",
    "                return \n",
    "            for i in range(n):\n",
    "                if check(nums,i):\n",
    "                    backtrack(nums+[i])\n",
    "        backtrack([])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        def solve(result, chess, row):\n",
    "            if row == len(chess):\n",
    "                zres = []\n",
    "                for i in chess:\n",
    "                    zres.append(''.join(i))\n",
    "                result.append(zres)\n",
    "                return\n",
    "            for i in range(len(chess)):\n",
    "                if valid(chess, row, i):\n",
    "                    chess[row][i] = 'Q'\n",
    "                    solve(result, chess, row + 1)\n",
    "                    chess[row][i] = '.'\n",
    "\n",
    "        def valid(chess, row, col):\n",
    "            for i in range(row):\n",
    "                if chess[i][col] == 'Q':\n",
    "                    return False\n",
    "            left_on = row - col # -1\n",
    "            right_on = row + col  # 5\n",
    "            for i in range(row):\n",
    "                if 0 <= i-left_on <= len(chess)-1 and chess[i][i-left_on] == 'Q':\n",
    "                    return False\n",
    "                if 0 <= right_on-i <= len(chess)-1 and chess[i][right_on-i] == 'Q':\n",
    "                    return False\n",
    "            return True\n",
    "        def main(n):\n",
    "            res1 = []\n",
    "            for i in range(n):\n",
    "                res2 = []\n",
    "                for j in range(n):\n",
    "                    res2.append('.')\n",
    "                res1.append(res2)\n",
    "            result = []\n",
    "            solve(result, res1, 0)\n",
    "            return result\n",
    "        a = main(n)\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        def generateBoard():\n",
    "            board = list()\n",
    "            for i in range(n):\n",
    "                row[queens[i]] = \"Q\"\n",
    "                board.append(\"\".join(row))\n",
    "                row[queens[i]] = \".\"\n",
    "            return board\n",
    "\n",
    "        def backtrack(row: int):\n",
    "            if row == n:\n",
    "                board = generateBoard()\n",
    "                solutions.append(board)\n",
    "            else:\n",
    "                for i in range(n):\n",
    "                    if i in columns or row - i in diagonal1 or row + i in diagonal2:\n",
    "                        continue\n",
    "                    queens[row] = i\n",
    "                    columns.add(i)\n",
    "                    diagonal1.add(row - i)\n",
    "                    diagonal2.add(row + i)\n",
    "                    backtrack(row + 1)\n",
    "                    columns.remove(i)\n",
    "                    diagonal1.remove(row - i)\n",
    "                    diagonal2.remove(row + i)\n",
    "                    \n",
    "        solutions = list()\n",
    "        queens = [-1] * n\n",
    "        columns = set()\n",
    "        diagonal1 = set()\n",
    "        diagonal2 = set()\n",
    "        row = [\".\"] * n\n",
    "        backtrack(0)\n",
    "        return solutions\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, N) -> ListNode:\n",
    "        # 用于放Queue的棋盘， 用的是二维列表，看题的时候没认真，没看到官方是一维的\n",
    "        # 我测试好了之后才发现是要返回一个二维列表，按照我下面的代码就是返回三维所以才有了result\n",
    "        # 下个版本再根据题目进行优化\n",
    "        checkerboard = [ [\".\" for j in range(N)]for i in range(N)]\n",
    "        # 题目要求的答案\n",
    "        result = []\n",
    "        \n",
    "        # 检查第row行 第col列是否可以放Queue\n",
    "        def check(row, col):\n",
    "            # 遍历到当前的行\n",
    "            # 只用考虑 row 及 小于row 的情况-因为后面的棋盘都是空的\n",
    "            for row_index in range(row):\n",
    "                # 当遍历到当前放置的行时进行判断， 是否已经放置了Queue\n",
    "                if row_index == row:\n",
    "                    if \"Q\" in checkerboard[row_index]:\n",
    "                        return False\n",
    "                # 判断遍历每行时，第col列是否已经放置了Queue\n",
    "                if \"Q\" == checkerboard[row_index][col]:\n",
    "                    return False\n",
    "            # 因为没看懂官方的 对角线 公式才有了下面的手动麻烦判断是否对角线存在Queue\n",
    "            # 为什么只判断斜上方同上面的原因一样-因为后面的棋盘都是空的\n",
    "            return check_left_up(row, col) and check_right_up(row, col)\n",
    "        \n",
    "        # 判断当前位置 左斜上方是否存在Queue\n",
    "        def check_left_up(row, col):\n",
    "            while row > 0 and col > 0:\n",
    "                row -= 1\n",
    "                col -= 1\n",
    "                if \"Q\" in checkerboard[row][col]:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        # 判断当前位置 右斜上方是否存在Queue\n",
    "        def check_right_up(row, col):\n",
    "            while row > 0 and col < N - 1:\n",
    "                row -= 1\n",
    "                col += 1\n",
    "                if \"Q\" in checkerboard[row][col]:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        # 把符合条件的棋盘加入result\n",
    "        def add_result():\n",
    "            tem_list = []\n",
    "            for each_row in checkerboard:\n",
    "                tem = \"\".join(each_row)\n",
    "                tem_list.append(tem)\n",
    "            result.append(tem_list)\n",
    "\n",
    "        # 主体函数\n",
    "        def input(row):\n",
    "            # 终止条件\n",
    "            if row >= N: add_result()\n",
    "            # 列的下标每次都从 0 ~ N-1 保证每种情况都试过\n",
    "            for input_col in range(N):\n",
    "                if check(row, input_col):\n",
    "                    checkerboard[row][input_col] = \"Q\"\n",
    "                    # 因为一行只会有一个Queue，所以该行放置了Queue后自然要从下一行开始，减少没有必要的尝试\n",
    "                    input(row + 1)\n",
    "                    # 这里很重要-也是模板里面提到的，进行尝试后如果不行一定要记得还原之前的操作\n",
    "                    checkerboard[row][input_col] = \".\"   \n",
    "        # 从第0行开始\n",
    "        input(0)\n",
    "        return result  \n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        chessboard=[['.']*n for _ in range(n)]\n",
    "        res=[]\n",
    "        def isValid(row, col):\n",
    "            count=0\n",
    "            for i in range(row):\n",
    "                if chessboard[i][col]=='Q':\n",
    "                    return False\n",
    "            i=row-1\n",
    "            j=col-1\n",
    "            while i>=0 and j>=0:\n",
    "                if chessboard[i][j]=='Q':\n",
    "                    return False\n",
    "                i-=1\n",
    "                j-=1\n",
    "            i=row-1\n",
    "            j=col+1\n",
    "            while i>=0 and j<n:\n",
    "                if chessboard[i][j]=='Q':\n",
    "                    return False\n",
    "                i-=1\n",
    "                j+=1\n",
    "            return True\n",
    "\n",
    "        def backtracking(row):\n",
    "            if row==n:\n",
    "                temp_res=[]\n",
    "                for temp in chessboard:\n",
    "                    temp_str=''.join(temp)\n",
    "                    temp_res.append(temp_str)\n",
    "                res.append(temp_res)\n",
    "                return\n",
    "            for col in range(n):\n",
    "                if isValid(row, col):\n",
    "                    chessboard[row][col]='Q'\n",
    "                    backtracking(row+1)\n",
    "                    chessboard[row][col]='.'\n",
    "        \n",
    "        backtracking(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        def isvalid(board, row, col):\n",
    "            for i in range(row):\n",
    "                if board[i][col] == 'Q':\n",
    "                    return False\n",
    "            i = row - 1\n",
    "            j = col + 1\n",
    "            while i >= 0 and j < len(board):\n",
    "                if board[i][j] == 'Q':\n",
    "                    return False\n",
    "                i -= 1\n",
    "                j += 1\n",
    "            i = row - 1\n",
    "            j = col - 1\n",
    "            while i >= 0 and j >= 0:\n",
    "                if board[i][j] == 'Q':\n",
    "                    return False\n",
    "                i -= 1\n",
    "                j -= 1\n",
    "            return True\n",
    "\n",
    "        def backtrack(board, row):\n",
    "            if row == len(board):\n",
    "                res.append([[j for j in i] for i in board])\n",
    "                return\n",
    "\n",
    "            for col in range(len(board)):\n",
    "                if not isvalid(board, row, col):\n",
    "                    continue\n",
    "                board[row][col] = 'Q'\n",
    "                backtrack(board, row + 1)\n",
    "                board[row][col] = '.'\n",
    "\n",
    "        res = []\n",
    "        board = [['.'] * n for i in range(n)]\n",
    "        backtrack(board, 0)\n",
    "        for i in range(len(res)):\n",
    "            for j in range(len(res[i])):\n",
    "                res[i][j] = ''.join(res[i][j])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        def dfs(i, tmp):\n",
    "            if i == n:\n",
    "                res.append(tmp)\n",
    "                return\n",
    "            for j in range(n):\n",
    "                if not (mark_c[j] or mark_d1[i+j] or mark_d2[i-j]):\n",
    "                    mark_c[j] = mark_d1[i+j] = mark_d2[i-j] = True\n",
    "                    dfs(i+1, tmp+['.'*j+'Q'+'.'*(n-j-1)])\n",
    "                    mark_c[j] = mark_d1[i+j] = mark_d2[i-j] = False\n",
    "\n",
    "        res = []\n",
    "        mark_c = [False for _ in range(n)]\n",
    "        mark_d1 = [False for _ in range(2*n-1)]\n",
    "        mark_d2 = [False for _ in range(2*n-1)]\n",
    "        dfs(0, [])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        def traceback(k):\n",
    "            if k == n:\n",
    "                generate_board()\n",
    "            else:\n",
    "                for i in range(n):\n",
    "                    if i not in columns and k-i not in diagonal1 and k+i not in diagonal2:\n",
    "                        columns.add(i)\n",
    "                        diagonal1.add(k-i)\n",
    "                        diagonal2.add(k+i)\n",
    "                        queens[k] = i\n",
    "                        traceback(k+1)\n",
    "                        columns.remove(i)\n",
    "                        diagonal1.remove(k-i)\n",
    "                        diagonal2.remove(k+i)\n",
    "\n",
    "        def generate_board() -> List[str]:\n",
    "            res = []\n",
    "            for i in range(n):\n",
    "                row[queens[i]] = 'Q'\n",
    "                res.append(''.join(row))\n",
    "                row[queens[i]] = '.'\n",
    "            solutions.append(res)\n",
    "            return res\n",
    "\n",
    "        solutions = []\n",
    "        queens = [-1] * n\n",
    "        row = ['.'] * n\n",
    "        columns = set()\n",
    "        diagonal1 = set()\n",
    "        diagonal2 = set()\n",
    "        traceback(0)\n",
    "        return solutions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        flag = [['.'] * n for _ in range(n)]\n",
    "        ans = []\n",
    "        def testfunc(k):\n",
    "            if k == n:\n",
    "                tmp = [''.join(flag[i]) for i in range(n)]\n",
    "                ans.append(tmp)\n",
    "                return \n",
    "            for i in range(n):\n",
    "                t = True\n",
    "                for j in range(k, -1, -1):\n",
    "                    if flag[j][i] == 'Q':\n",
    "                        t = False\n",
    "                        break\n",
    "                    r = k - j\n",
    "                    if i - r >= 0 and flag[j][i - r] == 'Q':\n",
    "                        t = False\n",
    "                        break\n",
    "                    if i + r < n and flag[j][i + r] == 'Q':\n",
    "                        t = False\n",
    "                        break\n",
    "                if t:\n",
    "                    flag[k][i] = 'Q'\n",
    "                    testfunc(k + 1)\n",
    "                    flag[k][i] = '.'\n",
    "        testfunc(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        def vaild(r,c):\n",
    "            for R in range(r):\n",
    "                C=col[R]\n",
    "                if r+c == R+C or r-c ==R-C:\n",
    "                    return False\n",
    "            return True\n",
    "        ans=[]\n",
    "        col=[0]*n\n",
    "        def dfs(r,s):\n",
    "            if r==n:\n",
    "                ans.append(['.'*c+'Q'+'.'*(n-1-c) for c in col])\n",
    "                return\n",
    "            for c in s:\n",
    "                if vaild(r,c):\n",
    "                    col[r]=c\n",
    "                    dfs(r+1,s-{c})\n",
    "        dfs(0,set(range(n)))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        def dfs(queens, xy_dif, xy_sum):\n",
    "            p = len(queens)\n",
    "            if p == n:\n",
    "                result.append(queens)\n",
    "                return None\n",
    "            for q in range(n):\n",
    "                if q not in queens and p - q not in xy_dif and p + q not in xy_sum:\n",
    "                    dfs(queens + [q], xy_dif + [p - q], xy_sum + [p + q])\n",
    "        \n",
    "        result = []\n",
    "        dfs([], [], [])\n",
    "        return [['.' * i + 'Q' + '.' * (n - i - 1) for i in sol] for sol in result]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkBoard(self,board, line, column):\n",
    "        n = len(board)\n",
    "\n",
    "        # check the line\n",
    "        for j in range(n):\n",
    "            if j != column and board[line][j] == 'Q':\n",
    "                return False\n",
    "\n",
    "        # check the column\n",
    "        for i in range(n):\n",
    "            if i != line and board[i][column] == 'Q':\n",
    "                return False\n",
    "\n",
    "        # check zigzag line\n",
    "        x = line\n",
    "        y = column\n",
    "\n",
    "        while x-1 >= 0 and y-1 >= 0:\n",
    "            if board[x-1][y-1] == 'Q':\n",
    "                return False\n",
    "\n",
    "            x = x-1\n",
    "            y = y-1\n",
    "\n",
    "        x = line\n",
    "        y = column\n",
    "\n",
    "        while x +1 < n and y + 1 < n:\n",
    "            if board[x + 1][y + 1] == 'Q':\n",
    "                return False\n",
    "\n",
    "            x = x + 1\n",
    "            y = y + 1\n",
    "\n",
    "        x = line\n",
    "        y = column\n",
    "\n",
    "        while x + 1 < n and y - 1 >= 0:\n",
    "            if board[x + 1][y - 1] == 'Q':\n",
    "                return False\n",
    "\n",
    "            x = x + 1\n",
    "            y = y - 1\n",
    "\n",
    "        x = line\n",
    "        y = column\n",
    "\n",
    "        while x - 1 >= 0 and y + 1 < n:\n",
    "            if board[x - 1][y + 1] == 'Q':\n",
    "                return False\n",
    "\n",
    "            x = x - 1\n",
    "            y = y + 1\n",
    "\n",
    "        return True\n",
    "\n",
    "\n",
    "    def backtracing(self,n,board,line,result):\n",
    "\n",
    "        if line == n:\n",
    "            temp = []\n",
    "            for i in range(n):\n",
    "                temp.append(''.join(board[i]))\n",
    "            result.append(temp)\n",
    "            return\n",
    "\n",
    "        for j in range(n):\n",
    "            if self.checkBoard(board,line,j):\n",
    "                board[line][j] = 'Q'\n",
    "                self.backtracing(n,board,line+1,result)\n",
    "                board[line][j] = '.'\n",
    "\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "\n",
    "        board = []\n",
    "        for _ in range(n):\n",
    "            board.append(['.']*n)\n",
    "        result = []\n",
    "        self.backtracing(n,board,0,result)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        res, rows, cols = [], set(), set()\n",
    "        lines1, lines2 = set(), set()\n",
    "        def isvalid(i, j):\n",
    "            if i not in rows and j not in cols and i-j not in lines1 and i+j not in lines2:\n",
    "                return True\n",
    "            return False\n",
    "        def backtrack(i, j, path):\n",
    "            if isvalid(i, j):\n",
    "                path.append((i,j))\n",
    "                if i==n-1:\n",
    "                    res.append(path[:])\n",
    "                    path.pop()\n",
    "                    return\n",
    "                rows.add(i)\n",
    "                cols.add(j)\n",
    "                lines1.add(i-j)\n",
    "                lines2.add(i+j)\n",
    "                for start in range(n):\n",
    "                    backtrack(i+1, start, path)\n",
    "                path.pop()\n",
    "                rows.remove(i)\n",
    "                cols.remove(j)\n",
    "                lines1.remove(i-j)\n",
    "                lines2.remove(i+j)\n",
    "        for j in range(n):\n",
    "            backtrack(0,j,[])\n",
    "        ans = []\n",
    "        for solu in res:\n",
    "            cur_solu = []\n",
    "            for node in solu:\n",
    "                solu_line = ['.' for _ in range(n)]\n",
    "                i, j = node\n",
    "                solu_line[j] = 'Q'\n",
    "                cur_solu.append(''.join(solu_line))\n",
    "            ans.append(cur_solu)\n",
    "        return ans\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        chessbroad = ['.'*n for _ in range(n)]\n",
    "        res = []\n",
    "        self.backtracking(chessbroad,res,0,n)\n",
    "        return res\n",
    "\n",
    "    def backtracking(self,chessbroad,res,row,n):\n",
    "        if row == n:\n",
    "            res.append(chessbroad[:])\n",
    "            return\n",
    "        for col in range(n):\n",
    "            if self.isVaild(chessbroad,row,col):\n",
    "                chessbroad[row] = chessbroad[row][:col]+'Q'+chessbroad[row][col+1:]\n",
    "                self.backtracking(chessbroad,res,row+1,n)\n",
    "                chessbroad[row] = chessbroad[row][:col]+'.'+chessbroad[row][col+1:]\n",
    "\n",
    "    \n",
    "    def isVaild(self,chessbroad,row,col):\n",
    "        for i in range (row):\n",
    "            if chessbroad[i][col] == 'Q':\n",
    "                return False\n",
    "        i,j = row-1,col-1\n",
    "        while i>=0 and j>=0:\n",
    "            if chessbroad[i][j] == 'Q':\n",
    "                return False\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "        \n",
    "        i = row-1\n",
    "        j = col+1\n",
    "        while i>=0 and j<len(chessbroad):\n",
    "            if chessbroad[i][j] == 'Q':\n",
    "                return False\n",
    "            i -= 1\n",
    "            j += 1\n",
    "            \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        ans_list = []\n",
    "        ans = []\n",
    "        def backtrack(n, row_id, column_pos):\n",
    "            # 所有行都遍历完了，添加进答案列表\n",
    "            if row_id == n:\n",
    "                ans_list.append(ans.copy())\n",
    "                return\n",
    "            # 根据之前行的Q位置，找到当前行不能踩的位置\n",
    "            forbid = []\n",
    "            for x, y in enumerate(column_pos):\n",
    "                forbid.append(y)\n",
    "                forbid.append(y - (row_id - x))\n",
    "                forbid.append(y + (row_id - x))\n",
    "            # 对能踩的位置进行递归\n",
    "            for i in range(n):\n",
    "                if i not in forbid:\n",
    "                    s = [\".\" for i in range(n)]\n",
    "                    s[i] = \"Q\"\n",
    "                    s = \"\".join(s)\n",
    "\n",
    "                    ans.append(s)\n",
    "                    column_pos.append(i)\n",
    "                    backtrack(n, row_id + 1, column_pos)\n",
    "                    column_pos.pop()\n",
    "                    ans.pop()\n",
    "\n",
    "        backtrack(n, 0, [])\n",
    "        return ans_list\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        m = n * 2 - 1\n",
    "        ans = []\n",
    "        col = [0] * n\n",
    "        on_path, diag1, diag2 = [False] * n, [False] * m, [False] * m\n",
    "        def dfs(r: int) -> None:\n",
    "            if r == n:\n",
    "                ans.append(['.' * c + 'Q' + '.' * (n - 1 - c) for c in col])\n",
    "                return\n",
    "            for c, on in enumerate(on_path):\n",
    "                if not on and not diag1[r + c] and not diag2[r - c]:\n",
    "                    col[r] = c\n",
    "                    on_path[c] = diag1[r + c] = diag2[r - c] = True\n",
    "                    dfs(r + 1)\n",
    "                    on_path[c] = diag1[r + c] = diag2[r - c] = False  # 恢复现场\n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        def generateBoard():\n",
    "            board = list()\n",
    "            for i in range(n):\n",
    "                row[queens[i]] = \"Q\"\n",
    "                board.append(\"\".join(row))\n",
    "                row[queens[i]] = \".\"\n",
    "            return board\n",
    "\n",
    "        def backtrack(row: int):\n",
    "            if row == n:\n",
    "                board = generateBoard()\n",
    "                solutions.append(board)\n",
    "            else:\n",
    "                for i in range(n):\n",
    "                    if i in columns or row - i in diagonal1 or row + i in diagonal2:\n",
    "                        continue\n",
    "                    queens[row] = i\n",
    "                    columns.add(i)\n",
    "                    diagonal1.add(row - i)\n",
    "                    diagonal2.add(row + i)\n",
    "                    backtrack(row + 1)\n",
    "                    columns.remove(i)\n",
    "                    diagonal1.remove(row - i)\n",
    "                    diagonal2.remove(row + i)\n",
    "                    \n",
    "        solutions = list()\n",
    "        queens = [-1] * n\n",
    "        columns = set()\n",
    "        diagonal1 = set()\n",
    "        diagonal2 = set()\n",
    "        row = [\".\"] * n\n",
    "        backtrack(0)\n",
    "        return solutions\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
